/*
 *  Copyright 2009 Advanced Industrial Science and Technology (AIST).
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/*! \file
 *  \brief
 */
#pragma once

#include <thrust/graph/detail/adjacency_list.hpp>
#include <thrust/graph/detail/reconstruct.hpp>

namespace thrust {
  
  //=============================
  // Directed Edges Helper Class
  //
  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  out_degree( typename Config::vertex_descriptor u,
              const directed_edges_helper<Config>& g_)
  {
    return out_degree( u, g_, thrust::called_from_host_tag());
  }
  
  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  out_degree( typename Config::vertex_descriptor u,
              const directed_edges_helper<Config>& g_,
              thrust::called_from_host_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;
    
    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex& sv =g.m_vertices[u];
    return sv.getOutDegree();
  }
  
  template <typename Config>
  __device__
  inline typename Config::degree_size_type
  out_degree( typename Config::vertex_descriptor u,
              const directed_edges_helper<Config>& g_,
              thrust::called_from_device_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;
    
    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex* sv =(g.ptr_vertices + u).get();
    return sv->getOutDegree();
  }
  
  template <typename Config>
  __host__
  inline thrust::pair<typename Config::out_edge_iterator,
                      typename Config::out_edge_iterator>
  out_edges( typename Config::vertex_descriptor u,
             directed_edges_helper<Config>& g_)
  {
    return out_edges( u, g_, thrust::called_from_host_tag());
  }

  template <typename Config>
  __host__
  inline thrust::pair<typename Config::out_edge_iterator,
                      typename Config::out_edge_iterator>
  out_edges( typename Config::vertex_descriptor u,
             directed_edges_helper<Config>& g_,
             thrust::called_from_host_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::out_edge_iterator out_edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    return g.get_out_edges( u, tag);
  }

  template <typename Config>
  __device__
  inline thrust::pair<typename Config::kernel_out_edge_iterator,
                      typename Config::kernel_out_edge_iterator>
  out_edges( typename Config::vertex_descriptor u,
             directed_edges_helper<Config>& g_,
             thrust::called_from_device_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::kernel_out_edge_iterator kernel_out_edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    return g.get_out_edges( u, tag);
  }
  
  //=============================
  // Directed Graph Helper Class

  template <typename Config>
  __host__ 
  inline thrust::pair<typename Config::edge_descriptor, bool>
  add_edge( typename Config::vertex_descriptor u,
            typename Config::vertex_descriptor v,
            directed_graph_helper<Config>& g_)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::edge_descriptor edge_descriptor;
    typedef typename Config::edge_iterator   edge_iterator;
    typedef typename Config::edge_parallel_category edge_parallel_category;

    Graph& g =static_cast<Graph&>(g_);
    bool inserted =true;
    
    edge_descriptor e( u, v);
    edge_iterator first, last, upper;
    if( detail::disallows_parallel( edge_parallel_category())){
      
      typedef thrust::detail::equal_edge<edge_descriptor> EqualEdge;
      
      thrust::tie( first, last) =g.get_out_edges();
      if( thrust::count_if( first, 
                            last, 
                            thrust::binder1st<EqualEdge>( EqualEdge(), e)
                            ) !=0)
        inserted =false;
    }

    if( inserted){
      g.add_out_edge( e);
    }
    
    return thrust::make_pair( e, inserted);
  }

  template <typename Config>
  __host__
  inline void
  remove_edge( typename Config::edge_descriptor e,
               directed_graph_helper<Config>& g_,
               bool erase_edge_flag)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    g.remove_out_edge( e, erase_edge_flag);
  }

  //===============================
  // UnDirected Graph Helper Class

  namespace detail
  {
    template <typename Config>
    __host__
    inline typename Config::degree_size_type
    out_degree( typename Config::vertex_descriptor u,
                const undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::StoredVertex StoredVertex;
      
      const Graph& g =static_cast<const Graph&>(g_);
      const StoredVertex& sv =g.m_vertices[u];
      
      return sv.getOutDegree();
    }
    
    template <typename Config>
    __host__
    inline typename Config::degree_size_type
    in_degree( typename Config::vertex_descriptor u,
               const undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::StoredVertex StoredVertex;
      
      const Graph& g =static_cast<const Graph&>(g_);
      const StoredVertex& sv =g.m_vertices[u];
      
      return sv.getInDegree();
    }
    
    template <typename Config>
    __host__
    inline thrust::pair<typename Config::edge_iterator,
                        typename Config::edge_iterator>
    out_edges( typename Config::vertex_descriptor u,
               undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_iterator edge_iterator;
      
      Graph& g =static_cast<Graph&>(g_);
      
      return g.get_out_edges(u, thrust::called_from_host_tag());
    }

    template <typename Config>
    __host__
    inline thrust::pair<typename Config::edge_iterator,
                        typename Config::edge_iterator>
    in_edges( typename Config::vertex_descriptor u,
              undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_iterator edge_iterator;
      
      Graph& g =static_cast<Graph&>(g_);
      
      return g.get_in_edges(u, thrust::called_from_host_tag());
    }

    template <typename Config>
    __host__
    inline thrust::pair<typename Config::edge_iterator,
                        typename Config::edge_iterator>
    in_edges( undirected_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_iterator edge_iterator;
      
      Graph& g =static_cast<Graph&>(g_);
      
      return g.get_in_edges();
    }

  } // end namespace detail

  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  out_degree( typename Config::vertex_descriptor u,
              const undirected_graph_helper<Config>& g_)
  {
    return out_degree( u, g_, thrust::called_from_host_tag());
  }
  
  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  out_degree( typename Config::vertex_descriptor u,
              const undirected_graph_helper<Config>& g_,
              thrust::called_from_host_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;

    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex& sv =g.m_vertices[u];
    
    return sv.getOutDegree() + sv.getInDegree();
  }

  template <typename Config>
  __device__
  inline typename Config::degree_size_type
  out_degree( typename Config::vertex_descriptor u,
              const undirected_graph_helper<Config>& g_,
              thrust::called_from_device_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;

    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex* sv =(g.ptr_vertices + u).get();
    
    return sv->getOutDegree() + sv->getInDegree();
  }

  template <typename Config>
  __host__
  inline thrust::pair<typename Config::out_edge_iterator,
                      typename Config::out_edge_iterator>
  out_edges( typename Config::vertex_descriptor u,
             undirected_graph_helper<Config>& g_)
  {
    return out_edges( u, g_, thrust::called_from_host_tag());
  }
  
  template <typename Config>
  __host__
  inline thrust::pair<typename Config::out_edge_iterator,
                      typename Config::out_edge_iterator>
  out_edges( typename Config::vertex_descriptor u,
             undirected_graph_helper<Config>& g_,
             thrust::called_from_host_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::out_edge_iterator out_edge_iterator;
    typedef typename Config::edge_iterator edge_iterator;

    Graph& g =static_cast<Graph&>(g_);

    edge_iterator out_first, out_last;
    thrust::tie( out_first, out_last) =g.get_out_edges( u, tag);
    
    edge_iterator in_first, in_last;
    thrust::tie( in_first, in_last) =g.get_in_edges( u, tag);

    return thrust::make_pair( out_edge_iterator( u
                                                 , out_first
                                                 , out_last
                                                 , in_first),
                              out_edge_iterator( u 
                                                 , in_last
                                                 , out_last
                                                 , in_first));
  }
  
  template <typename Config>
  __device__
  inline thrust::pair<typename Config::kernel_out_edge_iterator,
                      typename Config::kernel_out_edge_iterator>
  out_edges( typename Config::vertex_descriptor u,
             undirected_graph_helper<Config>& g_,
             thrust::called_from_device_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::kernel_out_edge_iterator kernel_out_edge_iterator;
    typedef typename Config::kernel_edge_iterator kernel_edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    
    kernel_edge_iterator out_first, out_last;
    thrust::tie( out_first, out_last) =g.get_out_edges( u, tag);
    
    kernel_edge_iterator in_first, in_last;
    thrust::tie( in_first, in_last) =g.get_in_edges( u, tag);
    
    return thrust::make_pair( kernel_out_edge_iterator( u
                                                        , out_first
                                                        , out_last
                                                        , in_first),
                              kernel_out_edge_iterator( u 
                                                        , in_last
                                                        , out_last
                                                        , in_first));
    /*return thrust::make_pair( kernel_out_edge_iterator(),
      kernel_out_edge_iterator());*/
  }
  
  template <typename Config>
  __host__ 
  inline thrust::pair<typename Config::edge_descriptor, bool>
  add_edge( typename Config::vertex_descriptor u,
            typename Config::vertex_descriptor v,
            undirected_graph_helper<Config>& g_)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::edge_descriptor edge_descriptor;
    typedef typename Config::edge_iterator   edge_iterator;
    typedef typename Config::edge_parallel_category edge_parallel_category;

    Graph& g =static_cast<Graph&>(g_);
    bool inserted =true;
    
    edge_descriptor e( u, v);
    edge_iterator first, last, upper;
    if( detail::disallows_parallel( edge_parallel_category())){
      
      typedef thrust::detail::equal_edge<edge_descriptor> EqualEdge;
      
      thrust::tie( first, last) =g.get_out_edges();
      if( thrust::count_if( first, 
                            last, 
                            thrust::binder1st<EqualEdge>( EqualEdge(), e)
                            ) !=0)
        inserted =false;
    }
    
    if( inserted){

      if( detail::out_degree( u, g) >detail::out_degree( v, g)){
        e.swap();
        g.add_out_edge( e);
        detail::reconstruct_in_edges( g, num_vertices( g), num_edges( g));
      }
      else{
        g.add_out_edge( e);
        detail::reconstruct_in_edges( g, num_vertices( g), num_edges( g));
      }

    }

    return thrust::make_pair( e, inserted);
  }

  template <typename Config>
  __host__
  inline void
  remove_edge( typename Config::edge_descriptor e,
               undirected_graph_helper<Config>& g_,
               bool erase_edge_flag)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    g.remove_out_edge( e, erase_edge_flag);

    e.swap();
    g.remove_out_edge( e, erase_edge_flag);

    detail::reconstruct_in_edges( g, num_vertices(g), num_edges(g));
  }
  //==================================
  // Bidirectional Graph Helper Class

  namespace detail {

    template <typename Config>
    __host__
    inline thrust::pair<typename Config::edge_iterator,
                        typename Config::edge_iterator>
    in_edges( bidirectional_graph_helper<Config>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_iterator edge_iterator;
      
      Graph& g =static_cast<Graph&>(g_);
      
      return g.get_in_edges();
    }
  } // end namespace detail

  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  in_degree( typename Config::vertex_descriptor u,
             const bidirectional_graph_helper<Config>& g_)
  {
    return in_degree( u, g_, thrust::called_from_host_tag());
  }

  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  in_degree( typename Config::vertex_descriptor u,
             const bidirectional_graph_helper<Config>& g_,
             thrust::called_from_host_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;
    
    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex& sv =g.m_vertices[u];
    return sv.getInDegree();
  }

  template <typename Config>
  __device__
  inline typename Config::degree_size_type
  in_degree( typename Config::vertex_descriptor u,
             const bidirectional_graph_helper<Config>& g_,
             thrust::called_from_device_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;
    
    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex* sv =(g.ptr_vertices + u).get();
    
    return sv->getInDegree();
  }

  template <typename Config>
  __host__
  inline thrust::pair<typename Config::in_edge_iterator,
                      typename Config::in_edge_iterator>
  in_edges( typename Config::vertex_descriptor u,
            bidirectional_graph_helper<Config>& g_)
  {
    return in_edges( u, g_, thrust::called_from_host_tag());
  }

  template <typename Config>
  __host__
  inline thrust::pair<typename Config::in_edge_iterator,
                      typename Config::in_edge_iterator>
  in_edges( typename Config::vertex_descriptor u,
            bidirectional_graph_helper<Config>& g_,
            thrust::called_from_host_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::in_edge_iterator in_edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    return g.get_in_edges( u, tag);
  }

  template <typename Config>
  __device__
  inline thrust::pair<typename Config::kernel_in_edge_iterator,
                      typename Config::kernel_in_edge_iterator>
  in_edges( typename Config::vertex_descriptor u,
            bidirectional_graph_helper<Config>& g_,
            thrust::called_from_device_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::kernel_in_edge_iterator kernel_in_edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    return g.get_in_edges( u, tag);
  }
 
  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  degree( typename Config::vertex_descriptor u,
          const bidirectional_graph_helper<Config>& g_)
  {
    return degree( u, g_, thrust::called_from_host_tag());
  }

  template <typename Config>
  __host__
  inline typename Config::degree_size_type
  degree( typename Config::vertex_descriptor u,
          const bidirectional_graph_helper<Config>& g_,
          thrust::called_from_host_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;
    
    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex& sv =g.m_vertices[u];
    
    return sv.getOutDegree() + sv.getInDegree();
  }
  
  template <typename Config>
  __device__
  inline typename Config::degree_size_type
  degree( typename Config::vertex_descriptor u,
          const bidirectional_graph_helper<Config>& g_,
          thrust::called_from_device_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::StoredVertex StoredVertex;
    
    const Graph& g =static_cast<const Graph&>(g_);
    const StoredVertex* sv =(g.ptr_vertices + u).get();
    
    return sv->getOutDegree() + sv->getInDegree();
  }

  template <typename Config>
  __host__ 
  inline thrust::pair<typename Config::edge_descriptor, bool>
  add_edge( typename Config::vertex_descriptor u,
            typename Config::vertex_descriptor v,
            bidirectional_graph_helper<Config>& g_)
  {
    std::cout <<"add_edge(bidirectionalS)" <<std::endl;

    typedef typename Config::graph_type Graph;
    typedef typename Config::edge_descriptor edge_descriptor;
    typedef typename Config::edge_iterator   edge_iterator;
    typedef typename Config::edge_parallel_category edge_parallel_category;

    Graph& g =static_cast<Graph&>(g_);
    bool inserted =true;
    
    edge_descriptor e( u, v);
    edge_iterator first, last, upper;
    if( detail::disallows_parallel( edge_parallel_category())){
      
      typedef thrust::detail::equal_edge<edge_descriptor> EqualEdge;
      
      thrust::tie( first, last) =g.get_out_edges();
      if( thrust::count_if( first, 
                            last, 
                            thrust::binder1st<EqualEdge>( EqualEdge(), e)
                            ) !=0)
        inserted =false;
    }
    
    std::cout <<"inserted: " <<inserted <<std::endl;

    if( inserted){
      g.add_out_edge( e);
      detail::reconstruct_in_edges( g, num_vertices( g), num_edges( g));
    }

    std::cout <<g.m_num_in_edges <<std::endl;
    return thrust::make_pair( e, inserted);
  }
  
  template <typename Config>
  __host__
  inline void
  remove_edge( typename Config::edge_descriptor e,
               bidirectional_graph_helper<Config>& g_,
               bool erase_edge_flag)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    g.remove_out_edge( e, erase_edge_flag);
    
    detail::reconstruct_in_edges( g, num_vertices(g), num_edges(g));
  }

  //=============================
  // Adjacency List Helper Class

  namespace detail {
    
    template <typename Config, typename DirectedHelper>
    __host__ __device__
    inline typename Config::edges_size_type
    capacity_in_edges( const adj_list_helper<Config,DirectedHelper>& g_)
    {
      typedef typename Config::graph_type Graph;
      const Graph& g =static_cast<const Graph&>(g_);
      return g.get_capacity_in_edges();
    }
    
    template <typename Config, typename DirectedHelper>
    __host__ __device__
    inline typename Config::edges_size_type
    num_in_edges( const adj_list_helper<Config,DirectedHelper>& g_)
    {
      typedef typename Config::graph_type Graph;
      const Graph& g =static_cast<const Graph&>(g_);
      return g.get_num_in_edges();
    }
   
    template <typename Config, typename DirectedHelper>
    __host__
    inline thrust::pair<typename Config::edge_iterator,
                        typename Config::edge_iterator>
    all_out_edges( adj_list_helper<Config,DirectedHelper>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_iterator edge_iterator;
      
      Graph& g =static_cast<Graph&>(g_);
      return thrust::make_pair( edge_iterator( g.get_all_out_edges().first),
                                edge_iterator( g.get_all_out_edges().second));
    }
    
    template <typename Config, typename DirectedHelper>
    __host__
    inline thrust::pair<typename Config::edge_iterator,
                        typename Config::edge_iterator>
    all_in_edges( adj_list_helper<Config,DirectedHelper>& g_)
    {
      typedef typename Config::graph_type Graph;
      typedef typename Config::edge_iterator edge_iterator;
      
      Graph& g =static_cast<Graph&>(g_);
      return thrust::make_pair( edge_iterator( g.get_all_in_edges().first),
                                edge_iterator( g.get_all_in_edges().second));
    }
  } // end namespace detail

  template <typename Config, typename DirectedHelper>
  __host__
  thrust::pair<typename Config::adjacency_iterator,
               typename Config::adjacency_iterator>
  adjacent_vertices( typename Config::vertex_descriptor u,
                     adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::out_edge_iterator out_edge_iterator;
    typedef typename Config::adjacency_iterator adjacency_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    out_edge_iterator first, last;
    tie( first, last) =thrust::out_edges( u, g);
    
    return thrust::make_pair( adjacency_iterator( first, g),
                              adjacency_iterator( last, g));
  }
  
  template <typename Config, typename DirectedHelper>
  __device__
  thrust::pair<typename Config::kernel_adjacency_iterator,
               typename Config::kernel_adjacency_iterator>
  adjacent_vertices( typename Config::vertex_descriptor u,
                     adj_list_helper<Config,DirectedHelper>& g_, 
                     thrust::called_from_device_tag tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::kernel_out_edge_iterator  kernel_out_edge_iterator;
    typedef typename Config::kernel_adjacency_iterator kernel_adjacency_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    kernel_out_edge_iterator first, last;
    tie( first, last) =thrust::out_edges( u, g, tag);
    
    return thrust::make_pair( kernel_adjacency_iterator( first, g),
                              kernel_adjacency_iterator( last, g));
  }

  template <typename Config, typename DirectedHelper>
  __host__ __device__
  inline typename Config::vertices_size_type
  num_vertices( const adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    const Graph& g =static_cast<const Graph&>(g_);
    return g.get_num_vertices();
  }
  
  template <typename Config, typename DirectedHelper>
  __host__ __device__
  inline typename Config::vertices_size_type
  capacity_vertices( const adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    const Graph& g =static_cast<const Graph&>(g_);
    return g.get_capacity_vertices();
  }

  template <typename Config, typename DirectedHelper>
  __host__ __device__
  inline typename Config::edges_size_type
  num_edges( const adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    const Graph& g =static_cast<const Graph&>(g_);
    return g.get_num_out_edges();
  }
  
  template <typename Config, typename DirectedHelper>
  __host__ __device__
  inline typename Config::edges_size_type
  capacity_edges( const adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    const Graph& g =static_cast<const Graph&>(g_);
    return g.get_capacity_out_edges();
  }

  template <typename Config, typename DirectedHelper>
  __host__ __device__
  inline thrust::pair<typename Config::vertex_iterator,
                      typename Config::vertex_iterator>
  vertices( const adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    const Graph& g =static_cast<const Graph&>(g_);
    return thrust::make_pair( g.get_vertices().begin(), g.get_vertices().end());
  }
  
  template <typename Config, typename DirectedHelper>
  __host__
  inline thrust::pair<typename Config::vertex_iterator,
                      typename Config::vertex_iterator>
  vertices( const adj_list_helper<Config,DirectedHelper>& g_,
            thrust::called_from_host_tag)
  {
    return vertices( g_);
  }
   
  template <typename Config, typename DirectedHelper>
  __device__
  inline thrust::pair<typename Config::vertex_iterator,
                      typename Config::vertex_iterator>
  vertices( const adj_list_helper<Config,DirectedHelper>& g_,
            thrust::called_from_device_tag)
  {
    return vertices( g_);
  }
  
  template <typename Config, typename DirectedHelper>
  __host__ 
  inline typename Config::vertex_descriptor
  add_vertex( adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type Graph;
    Graph& g =static_cast<Graph&>(g_);
    
    return g.add_vertex();
  }
  
  /*template <typename Config, typename DirectedHelper>
  __host__
  inline void
  clear_vertex( typename Config::vertex_descriptor u,
		adj_list_helper<Config,DirectedHelper>& g_)
  {
    typedef typename Config::graph_type        Graph;
    typedef typename Config::edge_descriptor   edge_descriptor;
    typedef typename Config::out_edge_iterator out_edge_iterator;
    typedef typename Config::edge_iterator     edge_iterator;
    typedef typename Config::vertices_size_type vertices_size_type;

    Graph& g =static_cast<Graph&>(g_);
    
    {
      edge_iterator iter, last;
      thrust::tie( iter, last) =g.get_out_edges( u, thrust::called_from_host_tag());
      remove_edges( iter, last, g, false);
    }
    
    {
      edge_iterator first, last;
      thrust::tie( first, last) =edges( g);
      thrust::sort( first, 
		    last, 
		    thrust::detail::less_edge_target<edge_descriptor>());
      
      edge_iterator lower_0, upper_0, lower_max, upper_max;
      thrust::tie( first, last) =edges( g);
      thrust::tie( lower_0, upper_0)
	=thrust::equal_range( first, 
			      last, 
			      edge_descriptor( 0, u), 
			      thrust::detail::less_edge_target<edge_descriptor>());
      thrust::tie( lower_max, upper_max)
	=thrust::equal_range( first,
			      last,
			      edge_descriptor( thrust::numeric_limits<vertices_size_type>::max(), u),
			      thrust::detail::less_edge_target<edge_descriptor>());
      
      remove_edges( lower_0, upper_max, g, false);
    }
    }*/

  
  template <typename Config, typename DirectedHelper>
  __host__
  inline thrust::pair<typename Config::edge_iterator,
                      typename Config::edge_iterator>
  edges( adj_list_helper<Config,DirectedHelper>& g_)
  {
    return edges( g_, thrust::called_from_host_tag());
  }

  template <typename Config, typename DirectedHelper>
  __host__
  inline thrust::pair<typename Config::edge_iterator,
                      typename Config::edge_iterator>
  edges( adj_list_helper<Config,DirectedHelper>& g_,
         thrust::called_from_host_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::edge_iterator edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    return thrust::make_pair( edge_iterator( g.get_out_edges().first),
                              edge_iterator( g.get_out_edges().second));
  }

  template <typename Config, typename DirectedHelper>
  __device__
  inline thrust::pair<typename Config::kernel_edge_iterator,
                      typename Config::kernel_edge_iterator>
  edges( adj_list_helper<Config,DirectedHelper>& g_,
         thrust::called_from_device_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::kernel_edge_iterator kernel_edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    return thrust::make_pair( kernel_edge_iterator( g.get_out_edges().first),
                              kernel_edge_iterator( g.get_out_edges().second));
  }
    
  /*template <typename Config, typename DirectedHelper>
  __host__
  inline void
  remove_edges( const typename Config::edge_iterator& lower,
		const typename Config::edge_iterator& upper,
		adj_list_helper<Config,DirectedHelper>& g_,
		bool erase_edge_flag =false)
  {

    assert( upper - lower >=0);

    typedef typename Config::graph_type Graph;
    typedef typename Config::edge_iterator edge_iterator;
    typedef typename Config::edge_descriptor edge_descriptor;
    typedef typename Config::vertex_descriptor vertex_descriptor;

    typedef typename Config::StoredVertex StoredVertex;

    Graph& g =static_cast<Graph&>(g_);

    edge_descriptor e =*lower;
    vertex_descriptor u =source( e, g);
    g.remove_out_edges( lower, upper, u, erase_edge_flag);
    }*/

  /*template <typename Config, typename DirectedHelper>
  __host__
  inline void
  remove_edge( typename Config::edge_iterator e_iter,
	       adj_list_helper<Config,DirectedHelper>& g_,
	       bool erase_edge_flag =false)
  {
    remove_edges( e_iter, e_iter + 1, g_, erase_edge_flag);
    }*/
  
  /*template <typename Config, typename DirectedHelper>
  __host__
  inline void
  remove_edge( typename Config::edge_descriptor e,
	       adj_list_helper<Config,DirectedHelper>& g_,
	       bool erase_edge_flag =false)
  {
    typedef typename Config::graph_type Graph;
    typedef typename Config::edge_descriptor edge_descriptor;
    typedef typename Config::edge_iterator edge_iterator;
    
    Graph& g =static_cast<Graph&>(g_);
    edge_iterator first, last, lower, upper;
    thrust::tie( first, last) =g.get_edges();
    thrust::tie( lower, upper) 
      =thrust::equal_range( first, 
			    last, 
			    e, 
			    thrust::detail::less_edge_source<edge_descriptor>());
    
    if( lower !=upper)
      remove_edges( lower, upper, g_, erase_edge_flag);

    
      }*/
  
  template <typename Config, typename DirectedHelper>
  __host__
  inline void
  remove_edge( typename Config::vertex_descriptor u,
               typename Config::vertex_descriptor v,
               adj_list_helper<Config,DirectedHelper>& g,
               bool erase_edge_flag)
  {
    typedef typename Config::edge_descriptor edge_descriptor;
    edge_descriptor e =edge_descriptor( u, v);
    return remove_edge( edge_descriptor( u, v), g, erase_edge_flag);
  }

  namespace detail {
    
    // vertex property
    template <typename Config, typename DirectedHelper, typename Property>
    __host__ __device__
    inline typename thrust::property_map<typename Config::graph_type, Property>::type
    get_dispatch( adj_list_helper<Config,DirectedHelper>& g_, Property, 
                  thrust::vertex_property_tag)
    {
      typedef typename Config::graph_type Graph;
      typedef typename thrust::property_map<Graph,Property>::type PA;
      Graph& g =static_cast<Graph&>(g_);
      return PA( &g);
    }

    template <typename Config, typename DirectedHelper, typename Property>
    __host__ __device__
    inline typename thrust::property_map<typename Config::graph_type, Property>::const_type
    get_dispatch( const adj_list_helper<Config,DirectedHelper>& g_, Property, 
                  thrust::vertex_property_tag)
    {
      typedef typename Config::graph_type Graph;
      typedef typename thrust::property_map<Graph,Property>::type PA;
      const Graph& g =static_cast<const Graph&>(g_);
      return PA( &g);
    }
    
    // edge property
    template <typename Config, typename DirectedHelper, typename Property>
    __host__ __device__
    inline typename thrust::property_map<typename Config::graph_type, Property>::type
    get_dispatch( adj_list_helper<Config,DirectedHelper>& g, Property,
                  thrust::edge_property_tag)
    {
      typedef typename Config::graph_type Graph;
      typedef typename thrust::property_map<Graph,Property>::type PA;
      return PA();
    }

  } // namespace detail

  /*
   *  Implamantation of the PropertyGraph Interface
   */
  template <typename Config, typename DirectedHelper, typename Property>
  __host__ __device__
  inline typename thrust::property_map<typename Config::graph_type, Property>::type
  get( Property p, adj_list_helper<Config,DirectedHelper>& g)
  {
    typedef typename property_kind<Property>::type Kind;
    return detail::get_dispatch( g, p, Kind());
  }

  template <class Config, class DirectedHelper, class Property>
  __host__ __device__
  inline typename thrust::property_map<typename Config::graph_type, Property>::const_type
  get( Property p, const adj_list_helper<Config,DirectedHelper>& g)
  {
    typedef typename property_kind<Property>::type Kind;
    return detail::get_dispatch( g, p, Kind());
  }
  
  template <typename Config, typename DirectedHelper, typename Property, typename Key>
  __host__ __device__
  inline typename thrust::property_traits<
    typename thrust::property_map<typename Config::graph_type, Property>::type
    >::reference
  get( Property p, adj_list_helper<Config,DirectedHelper>& g, 
       const Key& key, thrust::called_from_device_tag tag)
  {
    typedef typename property_kind<Property>::type Kind;
    return get( get( p, g), key, tag);
  }

  template <typename Config, typename DirectedHelper, typename Property, typename Key>
  __host__ __device__
  inline typename thrust::property_traits<
    typename thrust::property_map<typename Config::graph_type, Property>::const_type
    >::reference
  get( Property p, const adj_list_helper<Config,DirectedHelper>& g, 
       const Key& key, thrust::called_from_device_tag tag)
  {
    typedef typename property_kind<Property>::type Kind;
    return get( get( p, g), key, tag);
  }
   
  template <typename Config, typename DirectedHelper, typename Property, typename Key>
   __host__
  inline typename thrust::property_traits<
    typename thrust::property_map<typename Config::graph_type, Property>::type
    >::reference
  get( Property p, adj_list_helper<Config,DirectedHelper>& g, const Key& key)
  {
    typedef typename property_kind<Property>::type Kind;
    return get( get( p, g), key, thrust::called_from_host_tag());
  }

  template <typename Config, typename DirectedHelper, typename Property, typename Key>
  __host__
  inline typename thrust::property_traits<
    typename thrust::property_map<typename Config::graph_type, Property>::const_type
    >::reference
  get( Property p, const adj_list_helper<Config,DirectedHelper>& g, const Key& key)
  {
    typedef typename property_kind<Property>::type Kind;
    return get( get( p, g), key, thrust::called_from_host_tag());
  }
  
  template <typename Config
            , typename DirectedHelper
            , typename Property
            , typename Key
            , typename Value>
  __host__
  inline void
  put( Property p, adj_list_helper<Config,DirectedHelper>& g_,
       const Key& key, const Value& value, thrust::called_from_host_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename thrust::property_map<Graph,Property>::type Map;
    
    Graph& g =static_cast<Graph&>(g_);
    Map pmap =get( p, g);
    put( pmap, key, value, thrust::called_from_host_tag());
  }

  template <typename Config
            , typename DirectedHelper
            , typename Property
            , typename Key
            , typename Value>
  __device__
  inline void
  put( Property p, adj_list_helper<Config,DirectedHelper>& g_,
       const Key& key, const Value& value, thrust::called_from_device_tag)
  {
    typedef typename Config::graph_type Graph;
    typedef typename thrust::property_map<Graph,Property>::type Map;
    
    Graph& g =static_cast<Graph&>(g_);
    Map pmap =get( p, g);
    put( pmap, key, value, thrust::called_from_device_tag());
  }

  template <typename Config
            , typename DirectedHelper
            , typename Property
            , typename Key
            , typename Value>
  __host__
  inline void
  put( Property p, adj_list_helper<Config,DirectedHelper>& g_,
       const Key& key, const Value& value)
  {
    put( p, g_, key, value, thrust::called_from_host_tag());
  }
  
  //==========================================================
  // Vertex Property Maps

  // Implemantation of vertex property_map
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>  
  __host__ __device__
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::adj_list_vertex_property_map() { }
  
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>
  __host__ __device__
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::adj_list_vertex_property_map( Graph* g)
    : m_g(g) { }
  
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>
  __host__
  inline Reference
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::operator[]( key_type v) const
  {
    const StoredVertex& const_sv =m_g->m_vertices[v];
    StoredVertex& sv =const_cast<StoredVertex&>(const_sv);
    Reference x =get_property_value( sv.m_property, Tag());
    return x;
  }
  
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>
  __host__
  inline Reference 
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::operator()( key_type v) const
  {
    return this->operator[](v);
  }
  
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>
  __host__ __device__
  inline void
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::dispatch_put( key_type k, const value_type& v, thrust::called_from_host_tag)
  {
    StoredVertex sv =m_g->m_vertices[k];
    get_property_value( sv.m_property, Tag()) =v;
    m_g->m_vertices[k] =sv;
  }
    
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>
  __device__
  inline void
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::dispatch_put( key_type k, const value_type& v, thrust::called_from_device_tag)
  {
    StoredVertex* sv =(m_g->ptr_vertices + k).get();
    get_property_value( sv->m_property, Tag()) =v;
  }
  
  template <typename Graph
            , typename ValueType
            , typename Reference
            , typename Tag>
  template <typename CalledSpace>
  __host__ __device__
  inline void
  adj_list_vertex_property_map<Graph,ValueType,Reference,Tag>
  ::put( key_type k, const value_type& v, CalledSpace tag)
  {
    dispatch_put( k, v, tag);
  }

  //==========================================================
  // Edge Property Maps

  // Implemantation of edge property_map
  template <typename Directed
            , typename ValueType
            , typename Reference
            , typename Vertex
            , typename Property
            , typename Tag>
  __host__
  inline Reference
  adj_list_edge_property_map<Directed,ValueType,Reference,Vertex,Property,Tag>
  ::operator[]( key_type &e) const
  {
    device_ptr<Property> ptr =e.get_property();
    Property p; // p is on host
    thrust::copy( ptr, ptr+1, &p);
    return get_property_value( p, Tag());
  }
  
  template <typename Directed
            , typename ValueType
            , typename Reference
            , typename Vertex
            , typename Property
            , typename Tag>
  __host__
  inline Reference
  adj_list_edge_property_map<Directed,ValueType,Reference,Vertex,Property,Tag>
  ::operator()( key_type &e) const
  {
    return this->operator[](e);
  }

  template <typename Directed
            , typename ValueType
            , typename Reference
            , typename Vertex
            , typename Property
            , typename Tag>
  __host__
  inline void
  adj_list_edge_property_map<Directed,ValueType,Reference,Vertex,Property,Tag>
  ::put( key_type e, const value_type& v, 
         thrust::called_from_host_tag)
  {
    device_ptr<Property> ptr =e.get_property();
    Property p; // p is on host
    thrust::copy( ptr, ptr+1, &p);
    get_property_value( p, Tag()) =v;      
    *ptr =p;
  }

  template <typename Directed
            , typename ValueType
            , typename Reference
            , typename Vertex
            , typename Property
            , typename Tag>
  __host__
  inline void
  adj_list_edge_property_map<Directed,ValueType,Reference,Vertex,Property,Tag>
  ::put( key_type e, const value_type& v, 
         thrust::called_from_device_tag)
  {
    device_ptr<Property> ptr =e.get_property();
    get_property_value( *ptr.get(), Tag()) =v;  
  }

  //======================================
  // Device Adjacency List Implementation
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ inline
  adj_list_impl<Graph,Config,DirectedHelper>
  ::adj_list_impl() 
    : m_num_vertices(0)
    , m_capacity_vertices(0)
    , m_num_out_edges(0)
    , m_num_in_edges(0)
    , m_capacity_out_edges(0)
    , m_capacity_in_edges(0)
  {
    ptr_vertices =thrust::device_pointer_cast<StoredVertex>(0);
    ptr_out_edges =thrust::device_pointer_cast<edge_descriptor>(0);
    ptr_in_edges  =thrust::device_pointer_cast<edge_descriptor>(0);
  }
    
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ inline
  adj_list_impl<Graph,Config,DirectedHelper>
  ::adj_list_impl( vertices_size_type num_vertices)
    : m_num_vertices(num_vertices)
    , m_capacity_vertices(num_vertices)
    , m_num_out_edges(0)
    , m_num_in_edges(0)
    , m_capacity_out_edges(0)
    , m_capacity_in_edges(0)
  {
    m_vertices.resize( num_vertices);
    ptr_vertices =&m_vertices[0];
    ptr_out_edges =thrust::device_pointer_cast<edge_descriptor>(0);
    ptr_in_edges  =thrust::device_pointer_cast<edge_descriptor>(0);
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ inline
  adj_list_impl<Graph,Config,DirectedHelper>
  ::adj_list_impl( vertices_size_type num_vertices, 
                   edges_size_type capacity_edges)
    : m_num_vertices(num_vertices)
    , m_capacity_vertices(num_vertices)
    , m_num_out_edges(0)
    , m_num_in_edges(0)
      //, m_capacity_out_edges(capacity_edges)
      //, m_capacity_in_edges(capacity_edges)
  {
    m_vertices.resize( num_vertices);
    ptr_vertices =&m_vertices[0];
    
    this->init( capacity_edges);
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ inline
  adj_list_impl<Graph,Config,DirectedHelper>
  ::~adj_list_impl()
  {
  }

  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline void
  adj_list_impl<Graph,Config,DirectedHelper>
  ::insert_out_edge( size_type ipos, edge_descriptor& e)
  {
    if( m_out_edges.size() >1){
      thrust::copy( m_out_edges.begin() + ipos, 
		    m_out_edges.end(), 
		    m_out_edges.begin() + ipos + 1);
    }
    
    if( !thrust::detail::same_property<edge_property_type,no_property>::value){
      if( m_edge_property.size() >1){
        thrust::copy( m_edge_property.begin() + ipos, 
                      m_edge_property.end(),
                      m_edge_property.begin() + ipos + 1);
        
        typedef thrust::tuple<typename EdgeContainer::iterator
          ,typename EdgePropertyContainer::iterator> IteratorTuple;
        typedef thrust::zip_iterator<IteratorTuple> ZipIterator;
        
        ZipIterator first( thrust::make_tuple( m_out_edges.begin(), m_edge_property.begin()));
        ZipIterator last( thrust::make_tuple( m_out_edges.end(), m_edge_property.end()));
        
        thrust::for_each( first, 
                          last, 
                          detail::set_edge_property<edge_descriptor,edge_property_type>()
                          );
      }
      e.set_property( &m_edge_property[ipos]);
    }
    
    m_out_edges[ipos] =e;
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline void
  adj_list_impl<Graph,Config,DirectedHelper>
  ::remove_out_edges( edge_iterator lower, 
                      edge_iterator upper,
                      vertex_descriptor u,
                      bool erase_edge_flag)
  {
    StoredVertex sv =m_vertices[u];
    sv.dec_out_edges( upper - lower);
    m_vertices[u] =sv;
    
    thrust::for_each( m_vertices.begin() + u + 1,
                      m_vertices.end(), 
                      dec_out_edge_shift<StoredVertex>( upper - lower));
    
    //
    // first,*,*,lower,*,*,*,upper,*,*,*,end;
    //
    edge_iterator first( m_out_edges.begin());
    edge_iterator last( m_out_edges.end());
    size_t upos =upper - first;
    size_t lpos =lower - first;
    thrust::copy( m_out_edges.begin() + upos, 
                  m_out_edges.end(), 
                  m_out_edges.begin() + lpos);
    
    m_num_out_edges -=(upper - lower);
    edge_iterator iter =first + m_num_out_edges;
    thrust::for_each( iter, last, detail::clear_edge<edge_descriptor>());
    
    if( !thrust::detail::same_property<edge_property_type,no_property>::value){
      
      thrust::copy( m_edge_property.begin() + upos, 
                    m_edge_property.end(),
                    m_edge_property.begin() + lpos);
      
      typedef thrust::tuple<typename EdgeContainer::iterator
        ,typename EdgePropertyContainer::iterator> IteratorTuple;
      typedef thrust::zip_iterator<IteratorTuple> ZipIterator;
      
      ZipIterator zip_first( thrust::make_tuple( m_out_edges.begin(), m_edge_property.begin()));
      ZipIterator zip_last( thrust::make_tuple( m_out_edges.end(), m_edge_property.end()));
      
      thrust::for_each( zip_first, 
                        zip_last, 
                        detail::set_edge_property<edge_descriptor,edge_property_type>()
                        );
    }
    
  }

  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  inline typename Config::VertexContainer& 
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_vertex_container()
  {
    return m_vertices;
  }

  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline typename Config::EdgeContainer&
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_edge_container()
  {
    return m_out_edges;
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline typename Config::vertices_size_type
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_num_vertices() const 
  { 
    return m_num_vertices;
  }
 
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline typename Config::vertices_size_type
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_capacity_vertices() const
  { 
    return m_capacity_vertices;
  }

  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline typename Config::edges_size_type
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_num_out_edges() const 
  { 
    return m_num_out_edges;
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline typename Config::edges_size_type
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_num_in_edges() const
  { 
    return m_num_in_edges;
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline typename Config::edges_size_type
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_capacity_out_edges() const 
  { 
    return m_capacity_out_edges;
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline typename Config::edges_size_type
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_capacity_in_edges() const 
  { 
    return m_capacity_in_edges;
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ __device__
  inline integer_range<typename Config::vertex_descriptor,thrust::device_space_tag>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_vertices() const
  {
    return integer_range<vertex_descriptor,device_space_tag>( 0, m_num_vertices);
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline  thrust::pair<typename Config::EdgeContainer::iterator,
                       typename Config::EdgeContainer::iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_out_edges()
  {
    return thrust::make_pair( m_out_edges.begin(), 
                              m_out_edges.begin() + m_num_out_edges);
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline  thrust::pair<typename Config::EdgeContainer::iterator,
                       typename Config::EdgeContainer::iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_in_edges()
  {
    std::cout <<"m_num_in_edges: " <<m_num_in_edges <<std::endl;
    
    return thrust::make_pair( m_in_edges.begin(),
                              m_in_edges.begin() + m_num_in_edges);
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline  thrust::pair<typename Config::EdgeContainer::iterator,
                       typename Config::EdgeContainer::iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_all_out_edges()
  {
    return thrust::make_pair( m_out_edges.begin(),
                              m_out_edges.end());
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline  thrust::pair<typename Config::EdgeContainer::iterator,
                       typename Config::EdgeContainer::iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_all_in_edges()
  {
    return thrust::make_pair( m_in_edges.begin(),
                              m_in_edges.end());
  }
  
  //
  // get out and in edges at vertex: u
  // 
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline thrust::pair<typename Config::edge_iterator,
                      typename Config::edge_iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_out_edges( vertex_descriptor u
                   , thrust::called_from_host_tag)
  {
    const StoredVertex& sv =m_vertices[u];
    return thrust::make_pair( edge_iterator( m_out_edges.begin() + sv.out_edges().first),
                              edge_iterator( m_out_edges.begin() + sv.out_edges().second));
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __device__
  inline thrust::pair<typename Config::kernel_edge_iterator,
                      typename Config::kernel_edge_iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_out_edges( vertex_descriptor u
                   , thrust::called_from_device_tag)
  {
    const StoredVertex* sv =(ptr_vertices + u).get();
    return thrust::make_pair( kernel_edge_iterator( ptr_out_edges + sv->out_edges().first),
                              kernel_edge_iterator( ptr_out_edges + sv->out_edges().second));
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline thrust::pair<typename Config::edge_iterator,
                      typename Config::edge_iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_in_edges( vertex_descriptor u
                  , thrust::called_from_host_tag)
  {
    const StoredVertex& sv =m_vertices[u];
    return thrust::make_pair( edge_iterator( m_in_edges.begin() + sv.in_edges().first),
                              edge_iterator( m_in_edges.begin() + sv.in_edges().second));
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __device__
  inline thrust::pair<typename Config::kernel_edge_iterator,
                      typename Config::kernel_edge_iterator>
  adj_list_impl<Graph,Config,DirectedHelper>
  ::get_in_edges( vertex_descriptor u
                  , thrust::called_from_device_tag)
  {
    const StoredVertex* sv =(ptr_vertices + u).get();
    return thrust::make_pair( kernel_edge_iterator( ptr_in_edges+ sv->in_edges().first),
                              kernel_edge_iterator( ptr_in_edges + sv->in_edges().second));
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline typename Config::vertex_descriptor
  adj_list_impl<Graph,Config,DirectedHelper>
  ::add_vertex()
  {
    m_vertices.resize( m_num_vertices + 1);
    ptr_vertices =&m_vertices[0];
    
    ++m_num_vertices;      
    return m_num_vertices;
  }
 
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline void
  adj_list_impl<Graph,Config,DirectedHelper>
  ::reassign_edge_property()
  {
    typedef typename EdgeContainer::iterator EdgeContainerIter;
    typedef typename EdgePropertyContainer::iterator EdgePropertyContainerIter;
    typedef typename thrust::tuple<EdgeContainerIter,EdgePropertyContainerIter> IteratorTuple;
    typedef thrust::zip_iterator<IteratorTuple> ZipIterator;
    
    ZipIterator first( thrust::make_tuple( m_out_edges.begin(), m_edge_property.begin()));
    ZipIterator last( thrust::make_tuple( m_out_edges.end(), m_edge_property.end()));
    
    thrust::for_each( first, 
                      last, 
                      detail::set_edge_property<edge_descriptor,edge_property_type>()
                      );
  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__ 
  inline void
  adj_list_impl<Graph,Config,DirectedHelper>
  ::add_out_edge( edge_descriptor& e)
  {
    edge_iterator first, last, upper;
    thrust::tie( first, last) =get_out_edges();
    upper =thrust::upper_bound( first,
                                last,
                                e,
                                thrust::detail::less_edge_source<edge_descriptor>());      
    
    if( m_capacity_out_edges <m_num_out_edges + 1){	
      ++m_capacity_out_edges;
      m_out_edges.resize( m_capacity_out_edges);
      
      if( !thrust::detail::same_property<edge_property_type,no_property>::value)
        m_edge_property.resize( m_capacity_out_edges);
    }
    insert_out_edge( upper - first, e);
    m_num_out_edges++;
    
    const Graph& g =static_cast<Graph&>(*this);
    vertex_descriptor u =source( e, g);
    
    StoredVertex sv =m_vertices[u];
    if( sv.m_out_edges.empty()){
      sv.set_out_edges( upper - first, upper - first + 1);
    }
    else{
      sv.inc_out_edges();
    }
    m_vertices[u] =sv;

    thrust::for_each( m_vertices.begin() + u + 1,
                      m_vertices.end(), 
                      inc_out_edge_shift<StoredVertex>());
    
    ptr_out_edges =thrust::device_pointer_cast<edge_descriptor>( &m_out_edges[0]);

  }
  
  template <typename Graph
            , typename Config
            , typename DirectedHelper>
  __host__
  inline void
  adj_list_impl<Graph,Config,DirectedHelper>
  ::remove_out_edge( typename Config::edge_descriptor e,
                     bool erase_edge_flag)
  {
    edge_iterator first, last, lower, upper;
    thrust::tie( first, last) =get_out_edges();
    thrust::tie( lower, upper) 
      =thrust::equal_range( first, 
                            last, 
                            e, 
                            thrust::detail::less_edge_source<edge_descriptor>());
    
    if( lower !=upper){
      const Graph& g =static_cast<Graph&>(*this);
      vertex_descriptor from =source( e, g);
      remove_out_edges( lower, upper, from, erase_edge_flag);
    }
  }
  
} // end namespace thrust
#include <thrust/graph/detail/adjacency_list.inl>
